// @algorithm @lc id=52 lang=cpp 
// @title n-queens-ii


// @test(4)=2
// @test(1)=1
class Solution {
public:
    int totalNQueens(int n) {
        int ans = 0;
        function<void(int,int,int,int)> dfs =
        [&](int row, int col, int left, int right){
            if(row == n){
                ans ++;
                return;
            }
            for(int mask = ((1<<n)-1) & (~(col|left|right));
                mask; mask &= mask-1 ){
                int c = mask & -mask;
                dfs(row+1, col|c, (left|c)<<1, (right|c)>>1);
            }
        };
        dfs(0, 0, 0, 0);
        return ans;
    }
};